package insertionSort;

import selectionSort.ArrayGenerator;
import selectionSort.SortingHelper;

import java.util.Arrays;

/**
 * 自己实现版本
 */
public class MyInsertionSort {
    public static <E extends Comparable<E>> void sort(E[] data) {
        //循环不变量：[0,i)为已排序，[i,n)为乱序。
        for (int i = 1; i < data.length; i++) {
            int j = i - 1;
            E tmp = data[i];
            //for跳出后，j+1为i所在的位置。
            //循环结束时，j+1必然为大于tmp的第一个数，j为≤tmp的第一个数。
            for (; j >= 0 && (tmp.compareTo(data[j]) < 0); j--)
                data[j + 1] = data[j];
            data[j + 1] = tmp;
        }
    }

    /**
     * 递归插入排序接口
     *
     * @param data
     * @param <E>
     */
    public static <E extends Comparable<E>> void sortRecursive(E[] data) {
        sortRecursiveHelper(data, 0, data.length - 1);
    }

    /**
     * 插入排序的递归版本。出口是data为空或者其长度为1.
     *
     * @param data
     * @param l
     * @param h
     * @param <E>
     */
    private static <E extends Comparable<E>> void sortRecursiveHelper(E[] data, int l, int h) {

        if (data == null || h - l + 1 <= 1)//如果长度<=1则直接返回，基本情况。
            return;
        sortRecursiveHelper(data, l, h - 1);//将[l,h-1]排序好
        E tmp = data[h]; //后面是排序最后一个元素
        int i;
        for (i = h - 1; i >= 0 && data[i].compareTo(tmp) > 0; i--)
            data[i + 1] = data[i];
        data[i + 1] = tmp;
    }

    public static void main(String[] args) {
        boolean recursive = true; //是否测试递归版本
        if (recursive)
            testR();
        else test();
    }

    /**
     * 递归接口测试
     */
    private static void testR() {
        int n = 1000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        SortingHelper.sortTest("MyInsertionSortR", arr);
    }

    /**
     * 迭代接口测试
     */
    private static void test() {

        int[] dataSize = {1000, 10000};
        for (int n : dataSize) {
            System.out.println("================");
            System.out.println("Random Array:");
            Integer[] data1 = ArrayGenerator.generateRandomArray(n, n);
            Integer[] data2 = Arrays.copyOf(data1, data1.length);

            SortingHelper.sortTest("InsertionSort", data1);
            SortingHelper.sortTest("SelectionSort", data2);
            System.out.println();

            System.out.println("Ordered Array:");
            Integer[] data3 = ArrayGenerator.generateOrderedArray(n);
            Integer[] data4 = Arrays.copyOf(data3, data3.length);
            SortingHelper.sortTest("InsertionSort", data3);
            SortingHelper.sortTest("SelectionSort", data4);
            System.out.println();
        }
    }
}
